package a10_动态规划;

/**
 * <p>
 * a31_打家劫舍3复习1
 * </p>
 *
 * @author flyduck
 * @since 2025/2/20
 */
public class a31_打家劫舍3复习1 {
    public int rob(TreeNode root) {
        int[] dp = traversal(root);
        return Math.max(dp[0],dp[1]);
    }

    //二叉树的话需要递归：
    // dp[0]表示不偷当前节点最大金额
    // dp[1]表示偷当前节点最大金额

    private int[] traversal(TreeNode node){
        if (node == null) {
            return new int[]{0,0};
        }

        int[] leftDp = traversal(node.left);
        int[] rightDp = traversal(node.right);

        //包含node节点
        int val1 = node.val + leftDp[0] + rightDp[0];

        //不包含node节点
        int val2 = Math.max(leftDp[0],leftDp[1]) + Math.max(rightDp[0],rightDp[1]);

        return new int[]{val2,val1};
    }
}
